Luồng cực đại là gì? Các công bố khoa học về Luồng cực đại

Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (sourc...

Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (source) đến một đỉnh đích (sink) sao cho lưu lượng này là lớn nhất có thể.

Trong một mạng lưới, các đỉnh biểu thị vị trí và các cạnh biểu thị đường truyền thông giữa các vị trí đó. Mỗi cạnh có một số liệu gọi là khả năng chứa lưu lượng (capacity) - tức là lưu lượng tối đa có thể truyền qua cạnh đó.

Luồng cực đại tìm cách phân phối lưu lượng từ đỉnh nguồn đến đỉnh đích sao cho:
1. Lưu lượng trên mỗi cạnh không vượt quá khả năng chứa của cạnh đó.
2. Tổng lưu lượng đi qua mạng lưới là lớn nhất.

Để tìm luồng cực đại, các thuật toán như thuật toán Ford-Fulkerson hoặc thuật toán Edmonds-Karp được sử dụng. Các thuật toán này đều dựa trên khái niệm "đường cắt" (cut) trong đồ thị và sử dụng việc tăng cường đường đi (augmenting path) để tăng giá trị lưu lượng truyền qua mạng lưới.
Để hiểu chi tiết hơn về luồng cực đại, ta cần biết thêm một số khái niệm và thuật ngữ liên quan.

1. Đồ thị mạng (Network graph): Đồ thị mạng được sử dụng để biểu diễn một hệ thống hay mạng gồm các vị trí (đỉnh) và các đường truyền thông (cạnh) giữa chúng. Đồ thị mạng bao gồm một đỉnh nguồn (s) và một đỉnh đích (t), cùng với các đỉnh và cạnh khác.

2. Khả năng chứa lưu lượng (Capacity): Mỗi cạnh trong đồ thị mạng có một giá trị thể hiện lưu lượng tối đa mà cạnh đó có thể truyền qua. Đây là một giá trị không âm và có thể khác nhau cho từng cạnh.

3. Luồng (Flow): Một luồng trên đồ thị mạng là một phân phối của lưu lượng từ đỉnh nguồn đến đỉnh đích qua các cạnh. Luồng trên một cạnh phải thỏa mãn các ràng buộc sau:
- Không vượt quá khả năng chứa của cạnh: Lưu lượng trên mỗi cạnh phải nhỏ hơn hoặc bằng khả năng chứa của cạnh đó.
- Cân bằng luồng tại các đỉnh ngoại trừ đỉnh nguồn và đích: Tổng lưu lượng đến một đỉnh (trừ đỉnh nguồn và đích) phải bằng tổng lưu lượng ra khỏi đỉnh đó.

4. Luồng cực đại (Maximum Flow): Luồng cực đại trên một đồ thị mạng là luồng có tổng lưu lượng trên các cạnh là lớn nhất có thể. Điều này có nghĩa là không thể tăng giá trị của luồng bằng cách phân phối lưu lượng khác.

Thuật toán Ford-Fulkerson và Edmonds-Karp là hai phương pháp được sử dụng để tìm luồng cực đại trên đồ thị mạng. Cả hai thuật toán này đều dựa trên việc tìm đường đi từ đỉnh nguồn đến đỉnh đích (đường cắt) có thể cung cấp một lượng lưu lượng khả dụng tiếp theo để tăng giá trị của luồng. Thuật toán tiếp tục tìm kiếm đường đi này và tăng giá trị lưu lượng cho đến khi không còn đường đi nữa. Khi đó, luồng đã đạt đến cực đại.

Luồng cực đại có ứng dụng trong nhiều lĩnh vực như mạng máy tính, điều độ giao thông, lập lịch công việc, v.v.

Danh sách công bố khoa học về chủ đề "luồng cực đại":

Nguồn gốc của các lớp sụn trong cộng hưởng từ (MRI) Dịch bởi AI
Journal of Magnetic Resonance Imaging - Tập 7 Số 5 - Trang 887-894 - 1997
Tóm tắt

Để hiểu nguồn gốc của sự xuất hiện lớp sụn trong hình ảnh MRI (hiệu ứng góc kỳ diệu), các thí nghiệm MRI vi mô (μMRI) được thực hiện với độ phân giải pixel 14 μm trên sụn khớp bình thường của chó ở các khớp vai. Các hình ảnh hai chiều về thời gian nghỉ spin-spin (T2) của nút sụn-xương tại hai góc (0° và 55°) được tính toán một cách định lượng. Một sự dị hướng T2 rõ rệt đã được quan sát như một chức năng của độ sâu của mô sụn. Khu vực bề mặt và các vùng sâu bộc lộ sự phụ thuộc định hướng mạnh mẽ của T2, trong khi khu vực trên giữa cho thấy ít sự phụ thuộc định hướng của T2. Ba vùng μMRI này tương ứng gần như với ba khu vực mô học trong mô sụn. Kết quả từ các đo đạc T2 đại diện thống nhất với những kết quả μMRI này. Các nghiên cứu của chúng tôi cho thấy sự xuất hiện lớp sụn trong MRI được gây ra bởi sự dị hướng T2 của mô. Chúng tôi cũng đề xuất rằng nguồn gốc phân tử của sự dị hướng T2 là tương tác lưỡng cực hạt nhân. Cấu trúc của mô sụn chỉ ra rằng lưới collagen xác định sự dị hướng T2 này. Các kết quả cho thấy rằng sự dị hướng T2 cung cấp một chỉ số gián tiếp nhưng nhạy cảm cho định hướng của các cấu trúc đại phân tử trong mô sụn. Những ứng dụng lâm sàng của sự dị hướng này được thảo luận.

#MRI #sụn #dị hướng T2 #tương tác lưỡng cực hạt nhân #cấu trúc đại phân tử
Ước lượng các giá trị cực trị nhiệt độ hàng ngày bị thiếu bằng cách tiếp cận hồi quy tối ưu hóa Dịch bởi AI
International Journal of Climatology - Tập 21 Số 11 - Trang 1305-1319 - 2001
Tóm tắt

Một biến thể của phương pháp hồi quy bình phương tối thiểu được phát triển và đánh giá nhằm ước lượng nhiệt độ tối đa và tối thiểu hàng ngày bị thiếu, đặc biệt là đối với các giá trị cực trị nhiệt độ. Phương pháp này tập trung vào việc thu được những ước lượng chính xác về số ngày vượt quá (ví dụ: số ngày có nhiệt độ tối đa hàng ngày lớn hơn hoặc bằng centiles 90) hàng năm, cũng như số lần sự kiện liên tiếp vượt quá, trong khi giới hạn sai số ước lượng liên quan đến từng giá trị đơn lẻ.

Hiệu suất của phương pháp này được so sánh với hai phương pháp hiện có đã được phát triển cho toàn bộ phân phối nhiệt độ. Trong các phương pháp hiện có này, các ước lượng nhiệt độ được dựa trên dữ liệu từ các trạm lân cận bằng cách sử dụng hoặc phương pháp hồi quy hoặc phương pháp dựa trên sự thay đổi nhiệt độ.

Việc đánh giá phương pháp của chúng tôi bằng cách sử dụng nhiệt độ tối thiểu lạnh và tối đa ấm cho thấy phần trăm trung vị của số lần vượt quá được xác định chính xác là 97% và phần trăm trung vị của số lần vượt quá liên tiếp được xác định chính xác là 98%. Các phương pháp hiện có khác có xu hướng đánh giá thấp cả số lần vượt quá đơn lẻ và liên tiếp. Sử dụng các quy trình này, các số lần vượt quá ước lượng thường ít hơn 80% so với những gì đã thực sự xảy ra.

Mặc dù phương pháp của chúng tôi được tinh chỉnh để ước lượng số lần vượt quá, độ chính xác ước lượng của các giá trị nhiệt độ tối đa hoặc tối thiểu hàng ngày riêng lẻ tương tự như các quy trình ước lượng khác. Sai số tuyệt đối trung vị (MAE) sử dụng tất cả các nhiệt độ lớn hơn hoặc bằng centiles 90 (T90) là −1.1°C cho mười trạm khí hậu đa dạng là 1.28°C cho phương pháp của chúng tôi, trong khi các phương pháp khác cho MAE lần lượt là 1.27 và 1.17°C. Tuy nhiên, về sai số trung vị, xu hướng đánh giá thấp của các phương pháp hiện có là rõ ràng với độ lệch lần lượt là −0.77 và −0.61°C. Phương pháp tối ưu hóa của chúng tôi tương đối không có thiên kiến khi sai số trung bình thu được là −0.12°C. Bản quyền © 2001 Hiệp hội Khí tượng Hoàng gia

Ước lượng dòng carbon bề mặt dựa trên bộ lọc Kalman chuyển đổi tổ hợp cục bộ với cửa sổ đồng hóa ngắn và cửa sổ quan sát dài: kiểm thử mô phỏng hệ thống quan sát trong GEOS-Chem 10.1 Dịch bởi AI
Geoscientific Model Development - Tập 12 Số 7 - Trang 2899-2914

Tóm tắt. Chúng tôi đã phát triển một hệ thống đồng hóa dữ liệu carbon để ước lượng các dòng carbon bề mặt. Hệ thống này sử dụng bộ lọc Kalman chuyển đổi tổ hợp cục bộ (LETKF) và mô hình vận chuyển khí quyển GEOS-Chem được dẫn động bởi phân tích lại các trường khí tượng của MERRA-1 dựa trên mô hình Hệ thống Quan sát Trái Đất Goddard phiên bản 5 (GEOS-5). Hệ thống đồng hóa này lấy cảm hứng từ phương pháp của Kang và cộng sự (2011, 2012), những người đã ước tính dòng carbon bề mặt trong một thí nghiệm mô phỏng hệ thống quan sát (OSSE) như là các tham số thay đổi trong việc đồng hóa CO2 khí quyển, sử dụng cửa sổ đồng hóa ngắn 6 giờ. Họ đã bao gồm đồng hóa các biến khí tượng tiêu chuẩn, để tổ hợp mang lại một thước đo của độ không chắc chắn trong việc vận chuyển CO2. Sau khi giới thiệu các kỹ thuật mới như 'định vị biến động' và tăng trọng số quan sát gần bề mặt, họ đã đạt được các dòng carbon bề mặt chính xác ở độ phân giải điểm lưới. Chúng tôi đã phát triển một phiên bản mới của bộ lọc Kalman chuyển đổi tổ hợp cục bộ liên quan đến phương pháp 'ra-vào tại chỗ' (RIP) để tăng tốc giai đoạn tăng vòng của đồng hóa dữ liệu bộ lọc Kalman tổ hợp (EnKF) (Kalnay và Yang, 2010; Wang và cộng sự, 2013; Yang và cộng sự, 2012). Giống như RIP, hệ thống đồng hóa mới sử dụng thuật toán 'làm mịn không chi phí' cho LETKF (Kalnay và cộng sự, 2007b), cho phép dịch chuyển nghiệm của bộ lọc Kalman tiến hoặc lùi trong cửa sổ đồng hóa mà không tốn chi phí nào. Trong sơ đồ mới, một 'cửa sổ quan sát' dài (ví dụ, 7 ngày hoặc lâu hơn) được sử dụng để tạo ra tổ hợp LETKF sau 7 ngày. Sau đó, bộ làm mịn RIP được dùng để tạo ra phân tích cuối cùng chính xác trong 1 ngày. Cách tiếp cận mới này có lợi thế là dựa trên cửa sổ đồng hóa ngắn, điều này giúp nó chính xác hơn, và được tiếp xúc với những quan sát tương lai trong 7 ngày, điều này cải thiện phân tích và tăng tốc giai đoạn tăng vòng. Cửa sổ đồng hóa và quan sát sau đó được lùi lên trước 1 ngày, và quy trình này được lặp lại. Điều này giảm đáng kể lỗi phân tích, cho thấy rằng phương pháp đồng hóa mới được phát triển có thể được sử dụng với các mô hình hệ thống Trái Đất khác, đặc biệt là để tận dụng tốt hơn các quan sát kết hợp với các mô hình này.

#Kalman filter #carbon flux estimation #atmospheric transport model #GEOS-Chem #data assimilation #Earth system models #observing system simulation experiment #meteorological fields #ensemble Kalman filter #variable localization #carbon cycle.
Ước lượng kênh cực đại kỳ vọng cho các hệ thống OFDM có méo phi tuyến
Bài báo đề xuất việc sử dụng bộ ước lượng kênh dựa trên thuật toán kỳ vọng-cực đại EM cho các hệ thống ghép kênh phân chia theo tần số trực giao OFDM có méo phi tuyến trên cơ sở xấp xỉ tuyến tính hóa sử dụng phân tích Bussgang mở rộng. Các kết quả phân tích và mô phỏng chứng minh rằng thuật toán đề xuất chỉ yêu cầu độ phức tạp tính vừa phải với số lần giải lặp nhỏ trong khi cải thiện rất đáng kể chất lượng ước lượng kênh so với các phương pháp ước lượng thông thường khác như sai số nhỏ nhất LSE hay sai số bình phương trung bình cực tiểu MMSE. Điều này cho phép thực hiện san bằng hiệu quả hơn và hệ thống do đó cải thiện đáng kể được tỉ lệ lỗi bit BER. Ngoài ra, bộ ước lượng EM-LSE có thể bảo đảm chất lượng ước lượng gần tương đương như bộ ước lượng EM-MMSE trong khi không yêu cầu thông tin đặc trưng thống kê của kênh pha-đinh, cho phép xây dựng bộ ước lượng mạnh trên cả kênh pha-đinh và kênh phi tuyến với độ phức tạp tính giảm thiểu. 
#Nonlinear distortion; Channel estimation; Expectation maximization; OFDM.
Thuật toán đẩy luồng trước tìm luồng cực đại trên mạng hỗn hợp mở rộng
Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Bài viết xây dựng mô hình mạng hỗn hợp mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả hơn. Kết quả chính của bài viết là thuật toán đẩy luồng trước tìm luồng cực đại và định lý luồng cực đại lát cắt cực tiểu tương ứng trên mạng hỗn hợp mở rộng.
#đồ thị #mạng #luồng #luồng cực đại #thuật toán
Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng
Đồ thị và mạng mở rộng là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. [7]. Kết quả chính của bài báo là nghiên cứu thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng, sử dụng thuật toán tìm đường đi nhanh nhất trên mạng giao thông mở rộng [6]. Trên sơ sở bài toán đối ngẫu trong [7], tác giả xây dựng thuật toán đưa tỉ lệ hàm mục tiêu hai bài toán đối ngẫu này tiến đến 1, và từ đó suy ra luồng cực đại đồng thời chi phí cực tiểu. Đây là thuật toán tính gần đúng với tỉ lệ xấp xỉ là (1+w) với w dương nhỏ tùy ý. Bài báo phân tích, chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.
#đồ thị #mạng #luồng đa phương tiện #tối ưu #xấp xỉ
Thuật toán đường đi tăng luồng tìm luồng cực đại trên mạng hỗn hợp mở rộng
Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Bài viết xây dựng mô hình mạng hỗn hợp mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả hơn. Kết quả chính của bài viết là thuật toán đường đi tăng luồng tìm luồng cực đại và định lý luồng cực đại lát cắt cực tiểu tương ứng trên mạng hỗn hợp mở rộng.
#đồ thị #mạng #luồng #luồng cực đại #thuật toán
ĐÁNH GIÁ KẾT QUẢ PHẪU THUẬT NỘI SOI QUA ĐƯỜNG NIỆU ĐẠO CẮT PHÌ ĐẠI LÀNH TÍNH TUYẾN TIỀN LIỆT BẰNG ĐIỆN LƯỠNG CỰC Ở BỆNH NHÂN CÓ BỆNH LÝ TIM MẠCH
Tạp chí Y học Việt Nam - Tập 505 Số 2 - 2021
Mục tiêu: Đánh giá kết quả phẫu thuật nội soi qua đường niệu đạo cắt phì đại lành tính tuyến tiền liệt bằng điện lưỡng cực ở bệnh nhân có bệnh lý tim mạch. Đối tượng và phương pháp nghiên cứu: Nghiên cứu mô tả hồi tiến cứu trên 63 bệnh nhân bị u phì đại lành tính tuyến tiền liệt (UPĐLTTTL) có bệnh lý tim mạch kèm theo được điều trị bằng cắt đốt nội soi qua đường niệu đạo bằng điện lưỡng cựctại bệnh viện Đại Học Y Hà Nội từ tháng 01 năm 2019 đến tháng 5 năm 2021. Kết quả: NC hồi cứu 63 BN,độ tuổi trung bình là 73.5 ± 9.1, bệnh lý tim mạch đồng mắc: tăng huyết áp (THA) 73%, rối loạn nhịp tim 19.1%, bệnh mạch vành 9.5%, đặt máy tạo nhịp 6.4%, 8 bệnh nhân dùng thuốc chống đông. Điểm IPSS và QoL trước mổ 22.5 ± 3.8 và 4.6 ± 0.7, trọng lượng tuyến tiền liệt 68.3 ± 31.8g, phân suất tống máu (EF) trên siêu âm tim 68.9 ± 6.0%. Thời gian phẫu thuật 55.3 ± 21.4 phút, thời gian hậu phẫu 6.4 ± 2.0 ngày. Không gặp biến chứng trong mổ. Không có trường hợp nào đau thắt ngực, khó thở hay phải can thiệp tim mạch. Ba trường hợp biến chứng sau mổ: 2 chảy máu và 1 đau tức chân 2 bên, tất cả đều được điều trị nội ổn định. Tái khám 1 tháng không có trường hợp nào phải nhập viện điều trị về tim mạch, 1 trường hợp tử vong do bệnh phổi tắc nghẽn mạn tính. Kết luận: Phẫu thuật nội soi qua đường niệu đạo cắt phì đại tiền liệt tuyến bằng điện lưỡng cực (B-TURP) là phương pháp an toàn, hiệu quả trong điều trị phì đại lành tính tuyến tiền liệt trên nhóm bệnh nhân có bệnh lý tim mạch.
#Tăng sản lành tính tuyến tiền liệt #nội soi cắt tuyến tiền liệt qua niệu đạo bằng điện lưỡng cực #nội soi cắt tuyến tiền liệt qua niệu đạo trong nước muối (TURIS)
Tổng số: 39   
  • 1
  • 2
  • 3
  • 4